The present invention relates to the technique of compiling software, particularly source code, according to the techniques known as xe2x80x9cearly evaluationxe2x80x9d or xe2x80x9cpartial evaluation.xe2x80x9d More specifically, the present invention relates to novel software constructs that are superimposed on source code by a programmer to facilitate efficient partial evaluation.
In computer science, there is a well-known basic dichotomy between whether a given quantity of code in a single program is executed at compilation time or at runtime. Whether individual steps in the code are executed at runtime or compilation time will have a significant effect on the overall efficiency of the code. Speaking very generally, to have certain operations occur at runtime makes for an appealingly simple code, but code that requires too many operations, such as table look-ups, at runtime will take orders of magnitude longer than an implementation which can perform some look-ups at compilation time. This is particularly true of library or middleware, that can be seen as providing a special-purpose language for doing certain kinds of operation (i.e., an image processing library can be seen as a special language for doing image processing). Most of the relative inefficiency comes from the inability of library code to make effective use of information available to users of the library; information that could be exploited at compilation time gets repeatedly rediscovered at runtime.
In order to overcome the problem of deciding whether the particular portions of a computer program should be executed at compilation time or runtime, one technique which has been developed recently is called xe2x80x9cpartial evaluation.xe2x80x9d An overview of partial evaluation can be found in the first three chapters of Ruf, xe2x80x9cTopics in Online Partial Evaluation,xe2x80x9d (Ph.D. thesis, Stanford University, 1993). The Ruf dissertation basically describes an automatic program, called a xe2x80x9cspecializer,xe2x80x9d which operates in conjunction with a compiler: the specializer looks at codes submitted thereto, and makes an automatic inference, based on what information is known at a particular time, whether to xe2x80x9cspecializexe2x80x9d various portions of the program at partial evaluation time. Basically, if the specializer determines that it has enough information to specialize a particular input of the original program at partial evaluation time, and it judges that such specialization will be worthwhile, it does so. The overall output of the specializer is a new, specialized program which, when applied to any input satisfying the description, computes the same result as the original program. However, because the specialized program performed certain computations at partial evaluation time, the specialized program runs faster than the original program did.
Although a specializer as disclosed in the Ruf dissertation makes some progress in optimizing the execution of complicated programs, the practical applicability of partial evaluation has proven to be quite limited. It remains difficult to develop code that is highly efficient for purposes of partial evaluation, and all but impossible to make such code also easy to maintain.
The present invention takes an approach different from the attempt at total automation of partial evaluation, such as described in the Ruf dissertation. The present invention posits an arrangement whereby the programmer originating code has available to him certain software constructs which are read by a xe2x80x9cpartial evaluator,xe2x80x9d which is in effect a pre-compiler, which gives the programmer direct control over the execution time of different parts of the original program. The constructs of the present invention allow a programmer authoring a program to declare at individual call sites within the original program whether the code associated with a particular construct should be executed at runtime or at partial evaluation time.
In the prior art, U.S. Pat. No. 5,535,392 discloses a system for compiling a source program using what is called xe2x80x9csmartxe2x80x9d recompilation. Fragments of the source code are allowed to contain xe2x80x9cinvocation specificxe2x80x9d information, which is generated during a coded generation phase of compilation. A hint generator attempts to preserve values of the invocation specific information between successive invocations of the compiler.
U.S. Pat. No. 5,583,988 discloses a method for performing runtime checking during program execution in a compiled environment. The invention detects a number of errors during runtime that cannot be found by a compiler at the precise moment that a respective C language restriction is violated. The invention provides the human user with a direct indication of the problem, thus saving debugging time. When source code is compiled, the invention allocates special data structures for every pointer, array, and structure object in the program. An association is made between each of these objects and its special data structure in a compiler symbol table. At runtime, these data structures contain status information about their associated objects.
U.S. Pat. No. 5,625,822 discloses a system for compiling a source program using xe2x80x9csmart recompilation.xe2x80x9d Fragments of executable code are allowed to contain xe2x80x9cinvocation specificxe2x80x9d information, which is generated during a code generation phase of compilation. A hint generator attempts to preserve values of the invocation specific information between successive invocations of the compiler. Generally, the technique includes generating a first global context table generated from a previous version of the source program, the first global context table being divided into a first group of fragments, and generating a second global context table from the source program to be recompiled, the second global context table being divided into a second group of fragments. A comparison function is used to search the sorted tables to identify fragments that may be equivalent.
U.S. Pat. No. 5,632,033 discloses a system for dynamic, runtime alteration of preset variable space relationships by a runtime GUI modification of object connections associated with the variable spaces. Arbitrary linkages between all variable spaces are established prior to runtime to allow initial conditions for variable resolution irrespective of anticipated or actual object connections. Thus, all variables associated with objects are prespecified and provided with initial values, so long as a value has been assigned to the variable in some object. When actual object relationships are indicated at runtime, these effect new variable space linkages. The initial and subsequent linkages are effected with pointer addresses within the respective variable spaces.
The dissertation by Ruf, xe2x80x9cTopics in Online Partial Evaluation,xe2x80x9d (Ph.D. Thesis Stanford University, 1993) has been described in detail above.
An annotation mechanism called xe2x80x9cfiltersxe2x80x9d is presented in the paper xe2x80x9cNew insights into partial evaluation: the Schism experiment,xe2x80x9d by C. Consel, presented at the European Symposium on Programming, 1988, and published as volume 300 of Lecture Notes in Computer Science, pages 236-246, by Springer-Verlag. The filter mechanism allows a programmer to annotate a procedure to indicate under what circumstances it should be specialized and what arguments should be used to specialize the function.
According to one aspect of the present invention, there is provided a method of processing a computer program, the program having a procedure therein. There is provided in the program a language construct that specifies that a specialization of the procedure should be created at a point of use of the procedure.
According to another aspect of the present invention, there is provided a method of processing a computer program. There is provided in the program a language construct that specifies that a computation associated with the language construct should be carried out before the program is run. The program is submitted to a partial evaluator before the program is compiled. The partial evaluator returns an error if any computation in an expression having the language construct associated therewith cannot be done by the partial evaluator.
According to another aspect of the present invention, there is provided a method of processing a computer program, comprising submitting an expression in the program to a partial evaluator. If the partial evaluator determines a value which can be substituted for the expression without changing the result of the program, the partial evaluator returns to the program a first language construct, and otherwise returns to the program a second language construct.
According to another aspect of the present invention, there is provided a method of processing a computer program defining therein a specific procedure. An expression in the program is submitted to a partial evaluator. If the partial evaluator determines the expression is the result of invoking the specific procedure, the partial evaluator returns to the program a first language construct, and otherwise returns to the program a second language construct.
According to another aspect of the present invention, there is provided a method of processing a computer program, comprising the steps of identifying a part of the program, having a procedure definition therein, that is known to require execution at run time. The program is submitted to a partial evaluator before the program is compiled. There is provided in the program a language construct that causes the partial evaluator to override the value of the procedure definition throughout the identify part of the program.
FIG. 1 provides a simple overview of the use of a partial evaluator according to the present invention.